package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-10
 */

/**
 * 给定一个单链表L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */

public class leetcode143 {

    public void reorderList(ListNode head) {

        if (head==null) return;

        //找到中点
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //断开连接
        ListNode head2 = slow.next;
        slow.next = null;

        //反转后半部分
        ListNode pre = null;
        ListNode cur = head2;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        head2 = pre;

        //合并链表
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (head!=null && head2!=null){
            l1_tmp = head.next;
            l2_tmp = head2.next;
            //head2跟在head后
            head.next = head2;
            head = l1_tmp;
            //head的下一个跟在head2后
            head2.next = head;
            head2 = l2_tmp;
        }
    }
}
